package version2024.medium;

import java.util.Scanner;
import java.util.Stack;

/**
 * @author sunhl
 * @Description: HJ70 矩阵乘法计算量估算 字符串, 栈
 * @Date: created in 2025/1/8 星期三 15:57
 * @Modified By:
 */
public class HJ70_MatrixMultiplicationCalcEstimation {
    // A是一个50×10的矩阵，B是10×20的矩阵，C是20×5的矩阵
    // ((AB)C) = 50 * 10 * 20 + 50 * 20 * 5 = 15000
    // x0 * y0 * y1 + x0 * y1 * y2
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) {
            // 矩阵个数
            int n = in.nextInt();
            // 矩阵行数和列数, 放在数组一列
            int a[][] = new int[n][2];
            for (int i = 0; i < n; i++) {
                a[i][0] = in.nextInt();
                a[i][1] = in.nextInt();
            }
            // 计算规则
            String s = in.next();
            if(!s.contains("(") && !s.contains(")")) {
                s = "(" + s + ")";
            }

            // 存放矩阵行数和列数
            Stack<Integer> stack = new Stack<>();
            int sum = 0;
            for (int i = s.length() - 1, j = n - 1; i >= 0; i--) {
                // 属于字母则把相应的矩阵列数和行数入栈
                if (s.charAt(i) >= 'A' && s.charAt(i) <= 'Z') {
                    stack.push(a[j][1]);
                    stack.push(a[j][0]);
                    j--;
                } else if (s.charAt(i) == '(') {
                    // 括号：推出计算
                    // 矩阵尺寸x0*y0
                    int x0 = stack.pop(), y0 = stack.pop();
                    // 矩阵尺寸x1*y1
                    int x1 = stack.pop(), y1 = stack.pop();
                    // 两个矩阵的乘法次数为x0*y0*y1或x0*x1*y1（其中y0==x1）
                    sum += x0 * y0 * y1;
                    // 把相乘后得到的矩阵列数入栈
                    stack.push(y1);
                    // 把相乘后得到的矩阵行数入栈
                    stack.push(x0);
                }
            }
            System.out.println(sum);
        }
    }
}
